'''
快速排序
20210818 Nasa
'''
from test57_class_stack import MyStack
from test24random_list import sjlb


def partition(ints, lr):
    l, r = lr
    # if l >= r:
    v = ints[l]
    m = l
    for i in range(l, r + 1):
        if ints[i] < v:
            m += 1
            ints[i], ints[m] = ints[m], ints[i]
    ints[m], ints[l] = ints[l], ints[m]
    return [l, m - 1], [m + 1, r]


def quick_sort(ints):
    stack = []
    # 原鸡下蛋
    a, b = partition(ints, [0, len(ints) - 1])
    # 看情况放入stack
    if a[0] < a[1]:
        stack.append(a)
    if b[0] < b[1]:
        stack.append(b)
    # 判断stack是否为空
    while len(stack) != 0:
        # 从stack取,partition()-->蛋
        p = stack.pop()
        a, b = partition(ints, p)
        # 看情况放入stack
        if a[0] < a[1]:
            stack.append(a)
        if b[0] < b[1]:
            stack.append(b)


if __name__ == '__main__':
    int_list = [5, 4, 5, 3, 4, 9, 1, 8]
    quick_sort(int_list)
    print(int_list)
    # rl = partition(int_list, [0, 0])
    # print(rl)
    # stack = []
    # stack.append(rl[0])
    # partition(int_list,stack.pop())
    # partition(int_list, [0, 3])
    # print(int_list)
    # partition(int_list, [5, 7])
    # print(int_list)
    # partition(int_list, [1, 3])
    # print(int_list)
